{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problem Set 3: Structured Perceptron\n",
    "====================\n",
    "\n",
    "In this problem set, you will implement a sequence labeling algorithm that is near state-of-the-art: structured perceptron. To do this, you will use several functions that you have written earlier, especially Viterbi and averaged perceptron.\n",
    "\n",
    "The problem set is designed to highlight the connection between structured perceptron and classification-based tagging. You will first write most of the pieces that you need while working in the framework of classification-based tagging. Your implementation will take various tagging algorithms as arguments, including both one-word-at-a-time classification based tagging, and Viterbi sequence labeling.\n",
    "\n",
    "One of the main reasons to prefer perceptron over hidden Markov models is the ability to use rich, overlapping features. You will design several feature functions throughout the assignment.\n",
    "\n",
    "Because structure perceptron is slower to train than the hidden Markov model, we will use smaller datasets in this assignment, focusing on sentences that contain the most common POS tags in English and Japanese."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from gtnlplib import preproc, tagger_base, scorer \n",
    "from gtnlplib import features, viterbi, constants, structure_perceptron, kaggle\n",
    "\n",
    "import os\n",
    "import matplotlib.pyplot as plt\n",
    "from collections import defaultdict\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "English tags: set([u'ADV', u'NOUN', u'ADP', u'PRON', u'PROPN', u'DET', u'PUNCT', u'VERB', u'AUX', u'ADJ'])\n",
      "Japanese tags: set([u'ADV', u'NOUN', u'PRON', u'DET', u'PUNCT', u'VERB', u'NUM', u'ADJ'])\n"
     ]
    }
   ],
   "source": [
    "## Demo\n",
    "## NOTE! These datafiles are different than in pset2. Don't copy over constants.py from that pset.\n",
    "all_tags = set()\n",
    "for i,(words, tags) in enumerate(preproc.conll_seq_generator(constants.TRAIN_FILE,max_insts=100000)):\n",
    "    for tag in tags:\n",
    "        all_tags.add(tag)\n",
    "print(\"English tags: {}\".format(all_tags))\n",
    "\n",
    "all_tags_ja = set()\n",
    "for i,(words, tags) in enumerate(preproc.conll_seq_generator(constants.JA_TRAIN_FILE,max_insts=100000)):\n",
    "    for tag in tags:\n",
    "        all_tags_ja.add(tag)\n",
    "print(\"Japanese tags: {}\".format(all_tags_ja))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Tagging as discriminative classification\n",
    "\n",
    "In pset 2, you performed part-of-speech tagging as generative classification, using Naive Bayes. Now you will perform discriminative classification, using average perceptron.\n",
    "\n",
    "In this section, we are only doing classification-based tagging, but we will write the code in a way that generalizes to Viterbi-based structure prediction. This means that all features are of the form $f(\\boldsymbol{w},y_m,y_{m-1},m)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.1** Implement `features.word_feats` to output features that are tuples `(y,constants.CURR_WORD_FEAT,w[m])` and `(y,constants.OFFSET)`.\n",
    "\n",
    "(*0.7 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('NOUN', '**OFFSET**'): 1, ('NOUN', '--CURR-WORD--', 'man'): 1}\n",
      "{('VERB', '--CURR-WORD--', 'the'): 1, ('VERB', '**OFFSET**'): 1}\n",
      "{('NOUN', '**OFFSET**'): 1}\n"
     ]
    }
   ],
   "source": [
    "print(features.word_feats(['The','old','man','the','boat'],'NOUN','ADJ',2))\n",
    "print(features.word_feats(['The','old','man','the','boat'],'VERB','NOUN',3))\n",
    "# note that we may need to handle m >= len(tokens)\n",
    "print(features.word_feats(['The','old','man','the','boat'],'NOUN','ADJ',5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.2** Reimplement `tagger_base.classifier_tagger` as follows:\n",
    "\n",
    "Inputs:\n",
    "\n",
    "- List of tokens to tag\n",
    "- Feature function, of the form $f(\\boldsymbol{w},y_m,y_{m-1},m)$\n",
    "- Defaultdict of weights\n",
    "- List of all candidate tags\n",
    "\n",
    "Outputs:\n",
    "\n",
    "- List of predicted tags\n",
    "- Score of predicted tag sequence $\\theta \\cdot f(\\boldsymbol{w},\\boldsymbol{y})$\n",
    "\n",
    "(*0.7 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "theta_clf_hand = defaultdict(float,\n",
    "                             {('NOUN',constants.OFFSET):0.1,\n",
    "                              ('PRON',constants.CURR_WORD_FEAT,'They'):1,\n",
    "                              ('PRON',constants.CURR_WORD_FEAT,'can'):-1,\n",
    "                              ('NOUN',constants.CURR_WORD_FEAT,'fish'):1,\n",
    "                              ('VERB',constants.CURR_WORD_FEAT,'fish'):0.5})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['They', 'can', 'fish']\n"
     ]
    }
   ],
   "source": [
    "w = 'They can fish'.split()\n",
    "print(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(tagger_base);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([u'PRON', u'NOUN', u'NOUN'], 2.2)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tagger_base.classifier_tagger(w,features.word_feats,theta_clf_hand,all_tags)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.3** The perceptron update requires computing the difference\n",
    "\n",
    "\\begin{align}\n",
    "& f(\\boldsymbol{w},\\boldsymbol{y}) - f(\\boldsymbol{w},\\hat{\\boldsymbol{y}})\\\\\n",
    "= & \\sum_{m=1}^M f(\\boldsymbol{w},y_m,y_{m-1},m) - f(\\boldsymbol{w},\\hat{y}_m,\\hat{y}_{m-1},m)\n",
    "\\end{align}\n",
    "\n",
    "Implement `tagger_base.compute_features` to compute $f(\\boldsymbol{w},\\boldsymbol{y})$, with the following arguments:\n",
    "\n",
    "- A list of words\n",
    "- A list of tags\n",
    "- A feature function, of the form $f(\\boldsymbol{w},y_m,y_{m-1},m)$.\n",
    "\n",
    "The output should be a dict of features and counts.\n",
    "\n",
    "*Boundary cases*: \n",
    "\n",
    "- When $m=0$, use the special case $y_{-1} = \\text{START}$, using `constants.START_TAG`. *Your current feature function will not test this, because it ignores $y_{m-1}$, but we will test it later*.\n",
    "- When $m=M$, use the special case $y_M = \\text{STOP}$, using `constants.END_TAG`. \n",
    "\n",
    "These boundary cases will be important when you incorporate Viterbi tagging.\n",
    "\n",
    "(*0.7 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(tagger_base);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('--END--', '**OFFSET**'): 1.0,\n",
       " ('DET', '**OFFSET**'): 2.0,\n",
       " ('DET', '--CURR-WORD--', 'the'): 2.0,\n",
       " ('NOUN', '**OFFSET**'): 2.0,\n",
       " ('NOUN', '--CURR-WORD--', 'boat'): 1.0,\n",
       " ('NOUN', '--CURR-WORD--', 'old'): 1.0,\n",
       " ('VERB', '**OFFSET**'): 1.0,\n",
       " ('VERB', '--CURR-WORD--', 'man'): 1.0}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tagger_base.compute_features('the old man the boat'.split(),\n",
    "                            ['DET','NOUN','VERB','DET','NOUN'],\n",
    "                            features.word_feats)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.4**\n",
    "\n",
    "Now you can implement the function `structure_perceptron.sp_update`. \n",
    "\n",
    "This will be very similar to your implementation of `perceptron.perceptron_update` in pset 1, but instead of calling `clf_base.predict`, you should call a function `tagger` which is passed in as an argument.\n",
    "\n",
    "(*0.7 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(structure_perceptron);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([u'PRON', u'NOUN', u'NOUN'], 2.2)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tagger_base.classifier_tagger('They can fish'.split(),\n",
    "                             features.word_feats,\n",
    "                             theta_clf_hand,\n",
    "                             all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "update = structure_perceptron.sp_update('They can fish'.split(),\n",
    "                               ['PRON','AUX','VERB'],\n",
    "                               theta_clf_hand,\n",
    "                               features.word_feats,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((u'NOUN', '--CURR-WORD--', 'fish'), -1.0)\n",
      "((u'NOUN', '**OFFSET**'), -2.0)\n",
      "(('AUX', '--CURR-WORD--', 'can'), 1.0)\n",
      "(('VERB', '--CURR-WORD--', 'fish'), 1.0)\n",
      "(('VERB', '**OFFSET**'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'can'), -1.0)\n",
      "(('AUX', '**OFFSET**'), 1.0)\n"
     ]
    }
   ],
   "source": [
    "for key,val in update.iteritems():\n",
    "    if val != 0:\n",
    "        print(key,val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.5**\n",
    "\n",
    "You are now ready to implement `structure_perceptron.estimate_perceptron`.\n",
    "\n",
    "Your implementation will be nearly identical to `perceptron.estimate_perceptron`, except for two things:\n",
    "\n",
    "- The input is now a list of (token-list, tag-list) tuples\n",
    "- Instead of calling `perceptron.perceptron_update`, you will call `structure_perceptron.sp_update`.\n",
    "\n",
    "Other aspects of the implementation, such as weight averaging, should be identical.\n",
    "\n",
    "(*0.7 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(features)\n",
    "reload(tagger_base)\n",
    "reload(structure_perceptron);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "toy_data = [('They can fish'.split(),['PRON','AUX','VERB']),\n",
    "            ('the old man the boat'.split(),['DET','NOUN','VERB','DET','NOUN'])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "theta_toy_one_inst,_ = structure_perceptron.estimate_perceptron(toy_data[:1],\n",
    "                                                                features.word_feats,\n",
    "                                                                tagger_base.classifier_tagger,\n",
    "                                                                1,\n",
    "                                                                all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('NOUN', '**OFFSET**'): 1, ('NOUN', '--CURR-WORD--', 'They'): 1}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "features.word_feats(toy_data[0][0],'NOUN','IGNORE',0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((u'PRON', '**OFFSET**'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'can'), -1.0)\n",
      "((u'AUX', '--CURR-WORD--', 'can'), 1.0)\n",
      "((u'VERB', '--CURR-WORD--', 'fish'), 1.0)\n",
      "((u'VERB', '**OFFSET**'), 1.0)\n",
      "(('NOUN', '**OFFSET**'), -2.999)\n",
      "((u'NOUN', '--CURR-WORD--', 'They'), -1.0)\n",
      "((u'AUX', '**OFFSET**'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'fish'), -1.0)\n",
      "((u'PRON', '--CURR-WORD--', 'They'), 1.0)\n"
     ]
    }
   ],
   "source": [
    "for feat,weight in theta_toy_one_inst.iteritems():\n",
    "    if weight != 0:\n",
    "        print(feat,weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9\n"
     ]
    }
   ],
   "source": [
    "theta_toy_one_inst,_ = structure_perceptron.estimate_perceptron(toy_data[:1],\n",
    "                                                                features.word_feats,\n",
    "                                                                tagger_base.classifier_tagger,\n",
    "                                                                10,\n",
    "                                                                all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((u'PRON', '**OFFSET**'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'can'), -1.0)\n",
      "((u'AUX', '--CURR-WORD--', 'can'), 1.0)\n",
      "((u'VERB', '--CURR-WORD--', 'fish'), 1.0)\n",
      "((u'VERB', '**OFFSET**'), 1.0)\n",
      "(('NOUN', '**OFFSET**'), -2.999)\n",
      "((u'NOUN', '--CURR-WORD--', 'They'), -1.0)\n",
      "((u'AUX', '**OFFSET**'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'fish'), -1.0)\n",
      "((u'PRON', '--CURR-WORD--', 'They'), 1.0)\n"
     ]
    }
   ],
   "source": [
    "for feat,weight in theta_toy_one_inst.iteritems():\n",
    "    if weight != 0:\n",
    "        print(feat,weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "theta_toy,_ = structure_perceptron.estimate_perceptron(toy_data,\n",
    "                                                     features.word_feats,\n",
    "                                                     tagger_base.classifier_tagger,\n",
    "                                                     1, all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((u'PRON', '--CURR-WORD--', 'man'), -0.5)\n",
      "((u'VERB', '--CURR-WORD--', 'man'), 0.5)\n",
      "((u'AUX', '--CURR-WORD--', 'can'), 1.0)\n",
      "((u'VERB', '**OFFSET**'), 1.5)\n",
      "((u'PRON', '--CURR-WORD--', 'boat'), -0.5)\n",
      "((u'NOUN', '--CURR-WORD--', 'old'), 0.5)\n",
      "((u'AUX', '**OFFSET**'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'fish'), -1.0)\n",
      "((u'DET', '--CURR-WORD--', 'the'), 1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'boat'), 0.5)\n",
      "((u'DET', '**OFFSET**'), 1.0)\n",
      "((u'PRON', '**OFFSET**'), -1.5)\n",
      "((u'NOUN', '--CURR-WORD--', 'can'), -1.0)\n",
      "((u'PRON', '--CURR-WORD--', 'old'), -0.5)\n",
      "((u'VERB', '--CURR-WORD--', 'fish'), 1.0)\n",
      "((u'PRON', '--CURR-WORD--', 'the'), -1.0)\n",
      "((u'NOUN', '--CURR-WORD--', 'They'), -1.0)\n",
      "((u'PRON', '--CURR-WORD--', 'They'), 1.0)\n",
      "(('NOUN', '**OFFSET**'), -1.999)\n"
     ]
    }
   ],
   "source": [
    "for feat,weight in theta_toy.iteritems():\n",
    "    if weight != 0:\n",
    "        print(feat,weight)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Deliverable 1.6 ** Let's train this tagger and evaluate it.\n",
    "\n",
    "(*0.5 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "training_set = [inst for inst in preproc.conll_seq_generator(constants.TRAIN_FILE)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3531"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(training_set)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cell below takes 30 seconds to run on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_avp,theta_hist = structure_perceptron.estimate_perceptron(training_set,\n",
    "                                                       features.word_feats,\n",
    "                                                       tagger_base.classifier_tagger,\n",
    "                                                       20,\n",
    "                                                       all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8129496402877698"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tagger_base.eval_tagging_model(constants.DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats,\n",
    "                               theta_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagging_model(constants.TEST_FILE_HIDDEN,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats,\n",
    "                               theta_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words-te.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8229494440948185"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this line\n",
    "scorer.accuracy(scorer.get_confusion(constants.TEST_FILE,'avp-words-te.preds'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's see how accuracy improved over training. \n",
    "You can use this function elsewhere in the notebook if you'd like to see the progress of your classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEACAYAAABfxaZOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGN1JREFUeJzt3XuQVOWZx/HvAwKGi2gkRO4DKJG4WUk0RqMmbbQUjVnW\nlKVQWUsrm7iJUddYVtBUahkra22s2hizsUxZrrGSTSIQiEq8kgSn1KRYWRGvXIYBJgwMKI4oIsrt\n2T/eM07T9Ex3z/T06e7396k6Nd2nT3c/0wy/885z3nPG3B0REYnDgLQLEBGRylHoi4hERKEvIhIR\nhb6ISEQU+iIiEVHoi4hEpKjQN7OZZrbGzNaZ2dw8j08ws2VmttLMVpnZhcn688zs/8zsRTNbYWbn\nlPsbEBGR4lmhefpmNgBYB5wLbAVWALPdfU3WNvcAK939HjObDjzm7pPN7GRgu7tvM7OTgCfdfXx/\nfTMiItKzYkb6pwHN7t7q7vuA+cCsnG0OAkclt48GtgC4+4vuvi25/SpwpJkNKkvlIiJSsiOK2GYc\nsDnrfhthR5DtVmCpmV0PDAXOy30RM7uU8NvAvl7WKiIifVSuA7lzgPvdfQLwZeDX2Q8mrZ3/AK4u\n0/uJiEgvFDPS3wJMzLo/PlmX7Z+BCwDcfbmZHWlmo9x9h5mNB34PXOHum/K9gZnpAkAiIr3g7lbK\n9sWM9FcAx5vZJDMbDMwGluRs00rS0kkO5A5JAv9o4BFgrrsvL1C4ljIt8+bNS72Gelr0eerzrNal\nNwqGvrsfAK4FlgKvAvPdfbWZ3WpmFyeb3QR808xWAb8BrkzWfweYCvybmb2QTOkc1atKRUSkz4pp\n7+DuTwCfyFk3L+v2auCsPM+7DbitjzWKiEiZ6IzcOpTJZNIuoa7o8ywvfZ7pKnhyVkWKMPNqqENE\npJaYGd4PB3JFRKROKPRFRCKi0BcRiYhCX0QkIgp9EZGIKPRFRCKi0BcRiYhCX0QkIgp9EZEKe+89\nWL06nfcu6to7IiJSvIMHob0dNmzIv+zcCQ0N8NJLMKjCf0tQl2EQEemF3bth48b8ob5xI4wcCVOm\nhGXq1K7bU6bAmDEwoAx9lt5chkGhLyKSR3ej9ZaW8PXtt8NoPV+wT54Mw4b1f40KfZEye+cd2Lat\n768zaBAMGdK1DB4c1llJ/12l3Hbv7r4Fs2lT96P1yZNh7NjyjNb7QqEvUmaXXw7PPtu3UZs77NsH\nH3zQtezdCwcOhPDP3Rlk3+/rut48f+DA8n1+/c0d9uyBXbvCDvqddw69nXu/8/a2bdUzWu+L3oS+\nDuSK9GDNGnjkEfj0p8v/2gcOhPDP3hFk7xh6Wp9v3a5dxW1X6DUHDOh+5zB8OIwYAUcdFZbubud7\nbMiQrt9s9u49PIi7C+5CtwcN6r6W7HWjR3etGz06BHy5euu1RCN9kW64h5Brbw9hEQN32L+/+x3E\n7t2FwzjfY2+/HV5/2LAwXfHgwZ53ED3dzl1X6dkv1UQjfZEy2rYthFQsgQ9hJD5oUFiGDy/va3fu\nNIYOPXTUL5Wl0BfpRksLHH982lXUj84WkaQrsm6WSPHWrw99X5F6otAX6cb69RrpS/1R6It0Q+0d\nqUcKfZFuaKQv9UihL5KHOzQ3q6cv9UehL5JHR0f4euyx6dYhUm4KfZE8Ovv5mksu9UahL5KHpmtK\nvVLoi+Shg7hSrxT6Inko9KVeKfRF8tAcfalXCn2RPNTTl3ql0BfJsWsXvPtuuNa6SL1R6IvkaGkJ\no3xN15R6pNAXyaHWjtQzhb5IDs3ckXpWVOib2UwzW2Nm68xsbp7HJ5jZMjNbaWarzOzCrMduMbNm\nM1ttZueXs3iR/qDQl3pWMPTNbABwF3ABcBIwx8xOzNnsB8ACd/8MMAe4O3nuJ4HLgOnAhcDdZuqU\nSnXTdE2pZ8WM9E8Dmt291d33AfOBWTnbHAQ6/5Lo0cCW5PY/APPdfb+7bwKak9cTqVrq6Us9Kyb0\nxwGbs+63Jeuy3QpcYWabgUeA67p57pY8zxWpGnv2wBtvwIQJaVci0j/K9YfR5wD3u/tPzOx04NeE\nVlDRGhsbP7ydyWTIZDJlKk2keBs3QkMDDByYdiUih2tqaqKpqalPr2Hu3vMGIcQb3X1mcv9mwN39\n9qxtXgEucPctyf0W4HPANwgb/yhZ/wQwz93/N+c9vFAdIpWwZAnccw88+mjalYgUZma4e0nHSYtp\n76wAjjezSWY2GJgNLMnZphU4LyliOjDE3Xck211uZoPNbDJwPPBcKQWKVJJm7ki9K9jecfcDZnYt\nsJSwk7jP3Veb2a3ACnd/BLgJuNfMvks4qHtl8tzXzGwh8BqwD7hGQ3qpZuvXw/TpaVch0n8Ktncq\nUoTaO1IlLrgAbrgBLryw8LYiaeuv9o5INDRdU+qdRvoiib17YcSIcJXNwYPTrkakMI30RfqgtRXG\njVPgS31T6IskOi+pLFLPFPoiCU3XlBgo9EUSCn2JgUJfJKGra0oMFPoiCU3XlBhoyqYIcOAADBsG\nHR0wdGja1YgUR1M2RXqprQ1GjVLgS/1T6Iug6ZoSD4W+CJq5I/FQ6Iug0Jd4KPRF0HRNiYdCXwRN\n15R4aMqmRM8dhg+HrVth5Mi0qxEpnqZsivTCtm1hjr4CX2Kg0JfoabqmxEShL9HTzB2JiUJfoqfQ\nl5go9CV6mq4pMVHoS/Q0XVNiotCXqLlDc7NG+hIPhb5EraMjfD322HTrEKkUhb5ErXO6ppV0eotI\n7VLoS9Q0c0dio9CXqCn0JTYKfYmaQl9io9CXqOkSDBIbhb5ETSN9iY1CX6K1axe8+y6MGZN2JSKV\no9CXaLW0wJQpmq4pcVHoS7TU2pEYKfQlWgp9iZFCX6Kl0JcYFRX6ZjbTzNaY2Tozm5vn8TvM7AUz\nW2lma82sI+ux283sFTN71czuLGfxIn2h6ZoSoyMKbWBmA4C7gHOBrcAKM3vY3dd0buPuN2Ztfy0w\nI7l9BvB5d/87MzPgL2b2BXd/uszfh0jJNNKXGBUz0j8NaHb3VnffB8wHZvWw/RzggeS2A0ea2ZHA\nRwg7me19qFekLPbsgTfegAkT0q5EpLKKCf1xwOas+23JusOY2USgAVgG4O7LgSagHdgCPOnua3tf\nrkh5bNwIkybBwIFpVyJSWeU+kDsbWOTuDmBmU4ETgbGEHcW5ZnZmmd9TpGRq7UisCvb0CSP0iVn3\nxyfr8pkNXJN1/xJgubvvATCzx4EzgL/kPrGxsfHD25lMhkwmU0RpIr2j0Jda1NTURFNTU59ew5JB\nefcbmA0E1hIO5LYDzwFz3H11znYnAo+5+5SsdZcB3wAuJPxW8TjwE3d/NOe5XqgOkXK65hqYPh2u\nuy7tSkR6z8xw95LOKS/Y3nH3A8C1wFLgVWC+u682s1vN7OKsTS8nHOTNtgjYALwMvAC8kBv4ImnQ\ndE2JVcGRfkWK0EhfKmzqVHj8cZg2Le1KRHqvNyN9hb5EZ+9eGDEiXGVz8OC0qxHpvX5p74jUm9ZW\nGDtWgS9xUuhLdFpaNHNH4qXQl+houqbETKEv0VHoS8wU+hIdTdeUmCn0JToa6UvMNGVTonLgAAwb\nBh0dMHRo2tWI9I2mbIoU0NYGo0Yp8CVeCn2Jivr5EjuFvkRF/XyJnUJfoqLQl9gp9CUqau9I7BT6\nEhWN9CV2mrIp0XCH4cNh61YYOTLtakT6TlM2RXqwbVuYo6/Al5gp9CUa6ueLKPQlIurniyj0JSIK\nfRGFvkRE7R0Rhb5ERCN9EYW+RMIdmpsV+iIKfYlCR0f4euyx6dYhkjaFvkShs59vJZ3GIlJ/FPoS\nBfXzRQKFvkRBoS8SKPQlCuvXa7qmCCj0JRItLRrpi4BCXyKh9o5IoNCXurdrF7z7LowZk3YlIulT\n6Evda2mBKVM0XVMEFPoSAbV2RLoo9KXuKfRFuij0pe5puqZIF4W+1D1N1xTpotCXuqf2jkiXokLf\nzGaa2RozW2dmc/M8foeZvWBmK81srZl1ZD02wcyeNLPXzOwVM5tYzm9ApCd79sAbb8CECWlXIlId\njii0gZkNAO4CzgW2AivM7GF3X9O5jbvfmLX9tcCMrJf4FfBDd19mZkOBg+UqXqSQjRth0iQYODDt\nSkSqQzEj/dOAZndvdfd9wHxgVg/bzwEeADCz6cBAd18G4O7vufv7faxZpGhq7YgcqpjQHwdszrrf\nlqw7TNK6aQCWJaumAW+b2WIze97MbjfTKTJSOQp9kUMVbO+UaDawyN096/XPIrR7NgMLgauA+8v8\nvtIH7vDWW7BhQ9fysY/B2WfDCSfU9pms69fDiSemXYVI9Sgm9LcA2Qdfxyfr8pkNXJN1vw1Y5e6t\nAGb2EPA58oR+Y2Pjh7czmQyZTKaI0qRY+/ZBa+uhwZ69uIe57FOmQEMDvPwyNDaG5519dli+8AX4\n1Kdqqz/e0gIXX5x2FSLl0dTURFNTU59ew7oG5d1sYDYQWEs4kNsOPAfMcffVOdudCDzm7lOy1g0A\nngfOc/c3zewXwAp3/3nOc71QHdXuvffgu98NgXjyyTBjRgjIoUMrW8PatbBu3eGhvnUrjB3bFey5\nyzHHHD6idw87imeegaefDl+3bYPPfz7sAM4+G049FYYMqdz3WKqpU+Hxx2HatLQrESk/M8PdS/pd\nvGDoJy88E/gp4RjAfe7+IzO7lRDgjyTbzAOGuPv3c557LnBHcvd54Gp335+zTU2H/u7dYTQ5Zgyc\nfjqsWhWWNWvCzJHOnUDnctxxfXu/N9+E1asPX7ZvD+2YadMOD/eJE2HQoL5/r9u3w7PPhh3AM8+E\nncypp3b9JnDGGTB8eN/fpxz27oURI8JVNgcPTrsakfLrt9Dvb7Uc+rt2wZe/HA4W3nvvoa2PvXtD\n8L/4YteOYNUqOOKIrh1A5w5h2rSwvpM7tLXlD/cPPoDp0w9fJk+ufOvlnXfgr3/t+k1g5Uo46SQ4\n66zwmYwb17WMHl3Z+pqb4fzzw7RNkXqk0K+wd96Biy4KgXvPPTCgiLlQ7rBlS9cOoHOHsHVrCMuG\nhhBSa9aEEXO+cB8zpnoPrr7/Pjz3XNgRbNoUvte2tvB1587wW864cTB+/KE7hOz7Rx5Z2nu6w/79\nYSf7wQddy1NPwW9/C3/8Y798qyKpU+hX0Ntvw8yZYaR+993FBX5Pdu2Cl14KQTllSgj3o48uS6lV\n44MPws5ty5ZDdwbZ99vbQ0tm3Lgwg2j//kODvHPJDfgBA8KxhcGDw9fO5eqr4aab0v7ORfqHQr9C\ndu6ECy6Az34Wfvaz6h1116KDB2HHjrAD2LGjK8Rzwzx3XS3NKBIpF4V+BXR0hD7xmWfCnXcq8EUk\nPb0JfV1lswRvvgnnnRdmqSjwRaQWKfSLtGMHnHtuCP0f/1iBLyK1SaFfhNdfhy99KczUuf12Bb6I\n1C6FfgHbt8M558CsWXDbbQp8EaltCv0etLdDJgOXXQY//KECX0Rqn0K/G1u2hMD/2tdg3ry0qxER\nKQ+Ffh5tbSHwr7oKfvCDtKsRESkfhX6Ov/0NvvjFcCbnLbekXY2ISHmV+4+o1LRNm8IsneuuC5dJ\nFhGpNxrpJzZsCC2dG25Q4ItI/VLoA488Eq4DP3cuXH992tWIiPSfqNs7+/aFvv3ChbB4cbgGvIhI\nPYs29Ftb4fLLYdSo8Ic/Ro1KuyIRkf4XZXvn4YfDZZEvvRSWLFHgi0g8ohrp790L3/sePPRQCP4z\nzki7IhGRyoom9DdsCO2csWNDO+ejH027IhGRyouivbN4MZx+erikwkMPKfBFJF51PdJ///3w91Ef\newwefTT08UVEYla3ob9+fbg65uTJoZ1Tb39kXESkN+qyvbNgQThI+/Wvw6JFCnwRkU51NdLfsydc\nQuFPf4InnoBTTkm7IhGR6lI3I/21a8PB2rfeguefV+CLiORTF6G/cmW4hMK3vw3z58PIkWlXJCJS\nnczd064BM/O+1PGtb8GkSbr+vYjExcxw95L+kGvNh/7+/eGEq+XLYcqUMhcmIlLFehP6Nd/eeeop\naGhQ4IuIFKPmQ3/hwjAfX0RECqvp9s6+fTBmTJitM2lSPxQmIlLFomvv/PnPcMIJCnwRkWLVdOgv\nWBCunCkiIsWp2fbO3r1w3HHw0kswfnw/FSYiUsWiau8sXQonnaTAFxEpRVGhb2YzzWyNma0zs7l5\nHr/DzF4ws5VmttbMOnIeH2Fmm83sv8pVuGbtiIiUrmB7x8wGAOuAc4GtwApgtruv6Wb7a4EZ7v6N\nrHV3AqOADne/Ps9zSmrvvP9+mLXz2mvhq4hIjPqrvXMa0Ozure6+D5gPzOph+znAA1lFnQKMBpaW\nUlhPnngCZsxQ4IuIlKqY0B8HbM6635asO4yZTQQagGXJfQP+E7gJKGlv1BO1dkREeqfc19OfDSzK\n6tVcAzzq7ltD/ncf/I2NjR/ezmQyZDKZvNu9917484d33lmmikVEakRTUxNNTU19eo1ievqnA43u\nPjO5fzPg7n57nm1XAte4+/Lk/q+Bs4CDwAhgEHC3u38/53lF9/QXL4af/zz8oRQRkZj1pqdfzEh/\nBXC8mU0C2gmj+Tl53vxE4OjOwAdw93/KevxK4JTcwC+VTsgSEem9gj19dz8AXEs4EPsqMN/dV5vZ\nrWZ2cdamlxMO8vab3bvhySfhkkv6811EROpXTZ2Ru2AB3H9/mL0jIhK7uj8jd+FCtXZERPqiZkb6\nu3aFSy5s2gTHHFOZukREqlldj/T/8Ac4+2wFvohIX9RM6C9YoBOyRET6qibaOzt3wsSJsHkzjBxZ\nwcJERKpY3bZ3liyBc85R4IuI9FVNhL5OyBIRKY+qb++89RY0NEBbG4wYUdm6RESqWV22dx58EM47\nT4EvIlIOVR/6OiFLRKR8qrq9s2MHTJ0KW7fCsGEpFCYiUsXqrr3z4IMwc6YCX0SkXKo69HVClohI\neVVte+f112HaNGhvh498JKXCRESqWF21dxYvhosuUuCLiJRT1Ya+TsgSESm/qmzvtLfDJz8Zvh55\nZIqFiYhUsbpp7yxaBF/5igJfRKTcqjL0dUKWiEj/qLr2TlsbnHxyaO0MHpxyYSIiVawu2juLFsGs\nWQp8EZH+UHWhrxOyRET6T1W1d1pb4dRTw7V2Bg1KuyoRkepW8+2d3/0OLrlEgS8i0l+qKvQXLlRr\nR0SkP1VN6G/YAK2tkMmkXYmISP2qmtBfuBC++lU44oi0KxERqV9VFfo6IUtEpH9Vzeyd445z2tpg\n4MC0qxERqQ01PXvn0ksV+CIi/a1qQl+zdkRE+l/VtHcOHHAGVM0uSESk+tV0e0eBLyLS/xS1IiIR\nUeiLiESkqNA3s5lmtsbM1pnZ3DyP32FmL5jZSjNba2YdyfqTzeyvZvayma0yMx2uFRFJUcHQN7MB\nwF3ABcBJwBwzOzF7G3e/0d0/7e6fAX4G/D556D3gCnf/FHAhcKeZHVXOb0AO19TUlHYJdUWfZ3np\n80xXMSP904Bmd291933AfGBWD9vPAR4AcPdmd29JbrcDrwMf61vJUoj+U5WXPs/y0ueZrmJCfxyw\nOet+W7LuMGY2EWgAluV57DRgUOdOQEREKq/clzebDSzynMn/ZjYG+BVwRZnfT0RESlDw5CwzOx1o\ndPeZyf2bAXf32/NsuxK4xt2XZ60bATQB/+7uD3bzHumfISYiUoNKPTmrmJH+CuB4M5sEtBNG83Ny\nN0oO7h6dE/iDgIeAX3YX+L0pWkREeqdgT9/dDwDXAkuBV4H57r7azG41s4uzNr2ccJA322XAWcBV\nWVM6/75MtYuISImq4to7IiJSGamfkVvoxC8pjZltMrMXk9+snku7nlpjZveZ2XYzeylr3TFmtjQ5\n8fBJMxuZZo21opvPcp6ZtSW/9a80s5lp1lhLzGy8mS0zs1eTE16vT9aX9POZaugXc+KXlOwgkElO\nljst7WJq0P2En8dsNwN/cvdPEKYj31LxqmpTvs8S4A53/0yyPFHpomrYfuBGdz8JOAP4TpKXJf18\npj3SL/XELynMSP/ftWa5+7PAWzmrZwG/TG7/EvjHihZVo7r5LCH8jEqJ3H2bu69Kbr8LrAbGU+LP\nZ9rhUPSJX1I0B540sxVm9s20i6kTo919O4T/eMDolOupdd9JrsX132qV9Y6ZNQAzgOXAx0v5+Uw7\n9KX8znT3U4GLCP+5zkq7oDqk2Q+9dzcw1d1nANuAO1Kup+aY2XBgEfCvyYg/9+exx5/PtEN/CzAx\n6/74ZJ30UnKNI9z9DeBBQgtN+ma7mX0cwMyOI1xDSnrB3d/IOmP/XuCzadZTa8zsCELg/4+7P5ys\nLunnM+3Q//DELzMbTDjxa0nKNdUsMxuajAIws2HA+cAr6VZVk4xD+85LgKuS21cCD+c+Qbp1yGeZ\nhFKnr6Kfz1L9AnjN3X+ata6kn8/U5+knU7Z+StgB3efuP0q1oBpmZpMJo3snnG39G32epTGz3wIZ\n4FhgOzCPcFb574AJQCtwmbvvTKvGWtHNZ3kOoRd9ENgE/EtnP1p6ZmZnAk8DLxP+jzvwfeA5YCFF\n/nymHvoiIlI5abd3RESkghT6IiIRUeiLiEREoS8iEhGFvohIRBT6IiIRUeiLiEREoS8iEpH/B4Sd\nYywUJD0WAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f48c143ef90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "tagger_base.plot_learning_curve(constants.DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats,\n",
    "                               theta_hist,\n",
    "                               all_tags);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These accuracies are not directly comparable with your HMM accuracies from pset2, since we are using a different dataset.\n",
    "\n",
    "Let's see how many features are active."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of active features: 19265\n"
     ]
    }
   ],
   "source": [
    "print(\"Number of active features: %d\"%len([val for val in theta_avp.values() if val != 0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.7** Now try it on Japanese. \n",
    "\n",
    "(*0.5 points for 4650 / 0.25 points for 7650*)\n",
    "\n",
    "As before, 4650 students can opt in to 7650 grading by doing the 7650 problems.\n",
    "\n",
    "Please set the `GRADING` variable in `constants.py` to the appropriate grading scheme. Note that CS7650 students must be graded by the CS7650 rubric."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "training_set_ja = [inst for inst in preproc.conll_seq_generator(constants.JA_TRAIN_FILE)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cell below takes approximately 40 seconds to run on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_avp_ja,theta_hist_ja =\\\n",
    "structure_perceptron.estimate_perceptron(training_set_ja,\n",
    "                                         features.word_feats,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         20,\n",
    "                                         all_tags_ja)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.790288213524728"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tagger_base.eval_tagging_model(constants.JA_DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats,\n",
    "                               theta_avp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'avp-words.ja.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagging_model(constants.JA_TEST_FILE_HIDDEN,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats,\n",
    "                               theta_avp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'avp-words-te.ja.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7513812154696132"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.JA_TEST_FILE,'avp-words-te.ja.preds'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 1.8 (for 7650)** As you can see from the cells here, this tagging model is less accurate for Japanese than it is for English. Why might that be? (I'm looking for an explanation that is based on quantitative facts about the datasets.) Put your answer in `text-answers.md`.\n",
    "\n",
    "(*0.5 points for 7650, optional for 4650*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2. Better features\n",
    "\n",
    "One simple way to improve tagging is to add better features to the classification-based tagger. \n",
    "\n",
    "**Deliverable 2.1** Let's start by adding features that include the final two characters of each word as an additional, suffix feature. Do this by implementing `word_suff_features` in `features.py`.\n",
    "\n",
    "(*0.5 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(constants)\n",
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('DET', '--CURR-WORD--', 'The'): 1, ('DET', '**OFFSET**'): 1, ('DET', '--SUFFIX--', 'he'): 1}\n",
      "{('NOUN', '--SUFFIX--', 'ld'): 1, ('NOUN', '**OFFSET**'): 1, ('NOUN', '--CURR-WORD--', 'old'): 1}\n",
      "{('NOUN', '**OFFSET**'): 1, ('NOUN', '--SUFFIX--', 'a'): 1, ('NOUN', '--CURR-WORD--', 'a'): 1}\n"
     ]
    }
   ],
   "source": [
    "print(features.word_suff_feats(['The','old','man','a','boat'],'DET','ADJ',0))\n",
    "print(features.word_suff_feats(['The','old','man','a','boat'],'NOUN','DET',1))\n",
    "print(features.word_suff_feats(['The','old','man','a','boat'],'NOUN','ADJ',3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.2** Let's see whether this improves accuracy.\n",
    "\n",
    "(*0.5 points for 4650, 0.25 points for 7650. Includes both English and Japanese evaluations.*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(features);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cell below takes 50 seconds to run on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_suff_avp,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set,\n",
    "                                         features.word_suff_feats,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         20,\n",
    "                                         all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EN dev set\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8439248601119105"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('EN dev set')\n",
    "tagger_base.eval_tagging_model(constants.DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_suff_feats,\n",
    "                               theta_suff_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words-suff.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagging_model(constants.TEST_FILE_HIDDEN,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_suff_feats,\n",
    "                               theta_suff_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words-suff-te.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8481225089154605"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you cannot run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.TEST_FILE,'avp-words-suff-te.preds'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is 3% better than the word-only feature set! That's pretty good for adding a single feature template. Now let's try Japanese. \n",
    "\n",
    "The cell below takes 45 seconds to execute on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_suff_avp_ja,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set_ja,\n",
    "                                         features.word_suff_feats,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         20,\n",
    "                                         all_tags_ja)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JA dev set\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8816866659190311"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('JA dev set')\n",
    "tagger_base.eval_tagging_model(constants.JA_DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_suff_feats,\n",
    "                               theta_suff_avp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'avp-words-suff.ja.preds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "10% better on Japanese! Why might that be?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagging_model(constants.JA_TEST_FILE_HIDDEN,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_suff_feats,\n",
    "                               theta_suff_avp_ja,\n",
    "                               all_tags,\n",
    "                               'avp-words-suff-te.ja.preds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8445672191528545"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.JA_TEST_FILE,'avp-words-suff-te.ja.preds'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.3 (7650)** Briefly explain why you think suffix features are so helpful in Japanese. No prior Japanese knowledge is assumed! You may want to look at the raw data, and consult some resources about Japanese that you can find from a quick Google search. Put your answer in `text-answers.md`.\n",
    "\n",
    "(*0.5 points for 7650, optional for 4650*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.4** Now implement word neighbor features. These are features that should link a given tag to the words than come before and after it. Implement this function in `features.word_neighbor_feats`, and make sure it gives the same results as in the example cell below. Pay attention to the boundary case at the end. See `constants.PRE_START_TOKEN` and `constants.POST_END_TOKEN`.\n",
    "\n",
    "(*0.5 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reload(constants)\n",
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('TAG', '--CURR-WORD--', 'The'): 1\n",
      "('TAG', '**OFFSET**'): 1\n",
      "('TAG', '--PREV-WORD--', '[[START]]'): 1\n",
      "('TAG', '--NEXT-WORD--', 'old'): 1\n",
      "\n",
      "('TAG', '**OFFSET**'): 1\n",
      "('TAG', '--NEXT-WORD--', 'man'): 1\n",
      "('TAG', '--PREV-WORD--', 'The'): 1\n",
      "('TAG', '--CURR-WORD--', 'old'): 1\n",
      "\n",
      "('TAG', '**OFFSET**'): 1\n",
      "('TAG', '--NEXT-WORD--', 'a'): 1\n",
      "('TAG', '--CURR-WORD--', 'man'): 1\n",
      "('TAG', '--PREV-WORD--', 'old'): 1\n",
      "\n",
      "('TAG', '**OFFSET**'): 1\n",
      "('TAG', '--CURR-WORD--', 'a'): 1\n",
      "('TAG', '--PREV-WORD--', 'man'): 1\n",
      "('TAG', '--NEXT-WORD--', 'boat'): 1\n",
      "\n",
      "('TAG', '**OFFSET**'): 1\n",
      "('TAG', '--NEXT-WORD--', '[[END]]'): 1\n",
      "('TAG', '--PREV-WORD--', 'a'): 1\n",
      "('TAG', '--CURR-WORD--', 'boat'): 1\n",
      "\n",
      "('TAG', '**OFFSET**'): 1\n",
      "('TAG', '--PREV-WORD--', 'boat'): 1\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for m in xrange(6):\n",
    "    feats = features.word_neighbor_feats(['The','old','man','a','boat'],'TAG','IGNORE',m)\n",
    "    for feat,count in feats.iteritems():\n",
    "        print('{}: {}'.format(feat,count))\n",
    "    print "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 2.5** Let's try it, in both English and Japanese.\n",
    "\n",
    "(*0.5 points for 4650, 0.25 points for 7650*)\n",
    "\n",
    "The code below takes 60 seconds to run on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_neighbor_avp,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set,\n",
    "                                         features.word_neighbor_feats,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         20,\n",
    "                                         all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EN dev set\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8577138289368506"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('EN dev set')\n",
    "tagger_base.eval_tagging_model(constants.DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_neighbor_feats,\n",
    "                               theta_neighbor_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words-neighbor.preds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even better for English than the suffix features! Let's try Japanese.\n",
    "\n",
    "The code below takes 60 seconds to run on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19\n"
     ]
    }
   ],
   "source": [
    "theta_neighbor_avp_ja,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set_ja,\n",
    "                                         features.word_neighbor_feats,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         20,\n",
    "                                         all_tags_ja)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JA dev set\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.8020634742626443"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('JA dev set')\n",
    "tagger_base.eval_tagging_model(constants.JA_DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_neighbor_feats,\n",
    "                               theta_neighbor_avp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'avp-words-neighbor.ja.preds')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The neighbor features don't help nearly as much in Japanese, compared to the impact they make in English."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BAKEOFF #1\n",
    "\n",
    "**Deliverable 2.6** Implement the best features that you can for English and Japanese.\n",
    "You can use the same features for each, or you can use different features.\n",
    "You can also train the model longer, if you think that will help.\n",
    "\n",
    "Make sure to save the output in the following files:\n",
    "\n",
    "- **English dev**: `avp-best.preds`\n",
    "- **English test**: `avp-best-te.preds`\n",
    "- **Japanese dev**: `avp-best.ja.preds`\n",
    "- **Japanese test**: `avp-best-te.ja.preds`\n",
    "\n",
    "Grading:\n",
    "- Full credit (0.5 pts) for **88%** accuracy on English dev set, half credit (0.25 pts) for **87%** dev set accuracy.\n",
    "- Full credit (0.5 pts) for **90%** accuracy on Japanese dev set, half credit (0.25 pts) for **89%** dev set accuracy.\n",
    "- +0.1 for beating my test set score on English\n",
    "- +0.1 for beating my test set score on Japanese\n",
    "- +0.2 for top English score in 4650\n",
    "- +0.2 for top English score in 7650\n",
    "- +0.2 for top Japanese score in 4650\n",
    "- +0.2 for top Japanese score in 7650\n",
    "\n",
    "If you want to use an external library that is not standard with Python, please ask. For this part of the assignment, we will be more open to the use of 3rd party code, as long as it can be incorporated into your feature function. Libraries that include models that were trained on POS-labeled data will not be allowed. **We must be able to run your code to regenerate your outputs.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Getting Started With Kaggle\n",
    "In this bakeoff and the one at the end of this problem set, you will submit your results on the test data to Kaggle, which will keep an updated leaderboard of the best taggers in the class.\n",
    "\n",
    "Above each code snippet that outputs a file that you need to submit to Kaggle will be a link inviting you to the competition.  *NOTE THERE ARE 4 SEPARATE COMPETITIONS*, one for each combo of English and Japanese with AVP and Structure Prediction.  Make sure to submit the correct file to the correct competition.\n",
    "\n",
    "Your Kaggle account needs to be registered with an @gatech.edu email to join.  Also, please make your display name your real name.\n",
    "\n",
    "The public leaderboard shows how your taggers compare to your classmates on 50% of the test data.  The final standings on 100% of the test data will be released after the competition is over."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### English"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29\n"
     ]
    }
   ],
   "source": [
    "# for my best classification-based tagger, I trained the model for 30 iterations\n",
    "# this took a few minutes\n",
    "theta_best_avp,theta_best_avp_hist =\\\n",
    "structure_perceptron.estimate_perceptron(training_set,\n",
    "                                         features.word_feats_competitive_en,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         30,\n",
    "                                         all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EN dev set\n",
      "0.893485211831\n"
     ]
    }
   ],
   "source": [
    "print('EN dev set')\n",
    "dev_results = tagger_base.eval_tagging_model(constants.DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats_competitive_en,\n",
    "                               theta_best_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words-best.preds')\n",
    "print(dev_results)\n",
    "tagger_base.apply_tagging_model(constants.TEST_FILE_HIDDEN,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats_competitive_en,\n",
    "                               theta_best_avp,\n",
    "                               all_tags,\n",
    "                               'avp-words-best-te.preds')\n",
    "\n",
    "# SUBMIT KAGGLE-avp-bakeoff1-en-test.csv TO https://kaggle.com/join/gtclassificationtaggingen\n",
    "kaggle.kaggle_output(constants.TEST_FILE_HIDDEN,\n",
    "                                tagger_base.classifier_tagger,\n",
    "                                features.word_feats_competitive_en,\n",
    "                                theta_best_avp,\n",
    "                                all_tags,\n",
    "                                'KAGGLE-avp-bakeoff1-en-test.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8873505349276274"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.TEST_FILE,'avp-words-best-te.preds'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Japanese"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29\n"
     ]
    }
   ],
   "source": [
    "theta_best_avp_ja,theta_best_avp_hist_ja =\\\n",
    "structure_perceptron.estimate_perceptron(training_set_ja,\n",
    "                                         features.word_feats_competitive_ja,\n",
    "                                         tagger_base.classifier_tagger,\n",
    "                                         30,\n",
    "                                         all_tags_ja)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAEACAYAAACznAEdAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHc1JREFUeJzt3XuclnWd//HXm4OoqIiokQgeQvOwZWqZ58bQoKIsfGTY\nqvCz2n6PXVfLcsHNfQC72mqbrpl20DxgmGi2KVkb5MKs5hFRSAkGREU5hHIQUtRg5rN/fK+Bm9s5\n3DNz33Mf5v18PO7H3Pd1X4fvNdfM9b6/h+u6FRGYmZn1KncBzMysMjgQzMwMcCCYmVnGgWBmZoAD\nwczMMg4EMzMDCgwESaMkLZa0RNKEFt4fJulBSQskzZa0Xzb9KEmPSnpW0nxJZ+csc5ukFyQ9I+lp\nSR8s3m6ZmVlHqb3rECT1ApYAI4BVwFxgbEQszpnnHmBGREyTVAdcEBHnSzoEaIqIZZLeC8wDDouI\nTZJuy5b5VUn2zMzMOqSQGsJxwNKIWB4RW4DpwJl58xwBzAGIiPrm9yNiaUQsy56vBl4F9ung9s3M\nrBsUckIeAryS83pFNi3XfGAMgKQxwG6SBubOIOk4oG9zQGSuyJqSrpHUt8OlNzOzoinWJ/RLgTpJ\n84BTgJVAY/ObWXPRHcD4nGUmRsThwEeAQcC7+ibMzKz79ClgnpXAsJzX+2fTtsmag84CkNQfOCsi\nNmWvdwceAC6LiLk5y6zJfm7J+hO+2dLGJflmS2ZmnRAR6sj8hdQQ5gLDJR0gaSdgLDAjdwZJgyQ1\nb/gy4NZsel/gPmBqfuexpMHZTwGfA55rrQARUbOPSZMmlb0M3jfvn/ev9h6d0W4gREQjcCEwC1gI\nTI+IRZKmSBqdzVYHNEhaDOwLXJlNPxs4GRjfwvDSOyUtABaQmoyu6NQemJlZURTSZERE/A54f960\nSTnPfwn8soXl7gTubGWdIzpUUjMzKykP+yyzurq6chehZGp538D7V+1qff86o90L08pNUlR6Gc3M\nKo0kogSdymZm1gM4EMzMDHAgmJlZxoFgZmaAA8HMzDIOBDMzAxwIZmaWcSCYmRngQDAzs4wDwczM\nAAeCmZllHAhmZgY4EMzMLONAMDMzwIFgZmYZB4KZmQEOBDMzyzgQzMwMcCCYmVnGgWBmZgD0KXcB\nzEpp9er0c/BgUIe+brxta9fCqlWFz9+7NwwcCIMGQb9+Xd/+li2wbh28/joMGwa77tr1dZo5EKwk\nNmyAuXPh5JO772S1ZQvMnw+PPQaPPpp+vvkm9OoFb78Nhx66/fH+96efhxwCe+zR8vo2b4bnn4eG\nBliyZMdHYyPsv39adyG2boX169OjX78UDLmPvffe/nzAAPjLX9IJf926FD7Nz5sfmzfDXnulsq9a\nBUccASeeCCeckH4OHVrcAOyJGhth+fJ0vKX0NzN0aAr3WqWIKHcZ2iQpKr2MlmzdCrNmwdSp8Lvf\npX+g55+Hs86C8ePTiaqYJ6lXX93x5P/003DwwTueGIcPT9vcsAGWLt3x5N7QkKbtscf2kOjbd/s8\nr72W1tccHrlBsvfenduXiLZP9mvXwsaNqUytBUZzaDRv/623YN687b+Hxx5LJ63m38EJJ8AxxxSn\nZpKv+Zg3NMBHP5q2s/POxd9OqUSk45z7N9H8/IUXYN9904eGiDRt7Vp43/t2/Jto/rsYNKiyQlgS\nEdGhEjkQrMsWLkwhMG1aar4YNw6++MX0CXblyjT99tvTyWP8eDjvvDRfR2zdCs89t+NJb926dBJq\nPul99KOtf9pvTVNT+oTd0JAeW7du/wcfNqw6Pw1GwIsv7hiWDQ1w1FEwYgR85jPw4Q8XXrtpycKF\n6ZjeeWf6PR19dKoRLloEH/jA9mNywgmpJlVub76Zwr+lE3/zp//80B8+/N2129bW09CQfp+HHgr7\n7Vd4MAweDN/+dlqm2BwI1m3Wr4e77konhVWr0kl+3Dg4/PCW54+AJ59MwXH33ekEMn48fP7z0L9/\ny+t//PHtJ7S5c2HIkO0nmRNPTNvqykmtJ3njjfT7nzkTfv3r9Pv99KdTOJx+Ouy2W/vrWLcuHfOp\nU1PfTPMxP+yw7fO8+SY89dSOYbTLLjsetyOPhE2bWm8Oy30015bya0gt1Zr23HN7uOefsNeuTSf4\nlpoN996767/f3JrGmjWFLzd3Lvz0p3DZZXDRRamGWiwOBAPSP/+aNe9uWuisiNRmvW4dLFgAd9wB\nv/89fPKT6aR++ukd+yT99tswY0Y6sTz6KIwZA1/4AqxYsf0ksnIlfOQj2z9pHn98qnFYcSxbBg88\nkB5PPAEnnQSjR6eAyK29bdmSQuT22+HBB+FTn0rHfMSIwo55RGo2bK7VPfpoOkkPGNDyST7/RL/H\nHtvDo60+lXXrUrPgfvu9+4R/6KGV3fa/ZEkKg1degRtugNNOK856SxYIkkYB15GGqd4SEVfnvT8M\nuBXYB1gHnBsRqyQdBfwI2B1oBL4TEfdkyxwITAf2AuYB50XE1ha27UDogOefh1Gj0j/yhg2pfXng\nwNb/+QYNgj592v6Utm5d+iQ+aFBqU//bv4Wzz06fyLpq9erUpHT//XDQQdsD4G/+JpXLSm/TptQP\n8Otfw29/m06qo0en4L7zztRmPn58OuYDBpS7tLUpAu67D77xjfT3/73vpRpxV5QkECT1ApYAI4BV\nwFxgbEQszpnnHmBGREyTVAdcEBHnSzoEaIqIZZLeSzrxHxYRmyTdDdwbEb+Q9CNgfkT8pIXtOxAK\n9NRT8NnPwqRJ8LWvpWl//WtqHmirar51a+th0Rwku+xS3n2z7tHYmGoMDzyQPlGfd176hG3dY/Nm\n+M534Mc/hgkT4OKLYaedOreuUgXC8cCkiPhk9noiELm1BEnPASMjYmX2emNEvOuzhKT5wFlZQLwG\nvCcimrJtTI6IUS0s40AowMyZ6Z/35pvhzDPLXRoz64qlS1MYvPhiakYaMaLj6+hMIBTSJTcEeCXn\n9YpsWq75wJisEGOA3SQNzCvccUDfLAwGARsioilnnSXoZ+8ZfvYzOP98+NWvHAZmteCQQ+A3v4Gr\nroKvfCU1161YUfrtFmuMxqVAnaR5wCnASlKfAQBZc9EdwPgibc9I7Y7f/S5cfjnU16eOQTOrDVL6\ngPenP6URdaeeCu+8U9ptFtJttxLIHTW+fzZtm4hYDZwFIKk/qVloU/Z6d+AB4LKImJvNv07SnpJ6\nZbWEd60z1+TJk7c9r6uro66uroBi17amJrjkEpg9O43c6GoHlJlVpl12gSlTUp9CWxcX1tfXU19f\n36VtFdKH0BtoIHUqrwaeBM6JiEU58wwC1kdESLoC2BoRkyX1BX4H3B8R1+et927gvyLi7qxTeUFE\n/LiF7bsPIc8776QmojVr0siEYoz2MbPaUpI+hIhoBC4EZgELgekRsUjSFEmjs9nqgAZJi4F9gSuz\n6WcDJwPjJT0j6WlJH8zemwhcImkJaejpLR0peLX7619T4l9xRfqU/8YbhS23cWMaVtrUlG4P4TAw\ns2LxhWll0NSUPuGvXZvG2z/2WLop26GH7nj/mYMP3vGislWr0sVgp54K111XuRfamFn5+UrlKjFx\nIjz0ULrys/leKe+8A888s/1qzkcfTdcHNF/yf9hh8PWvp+sLJkyorJtomVnlcSBUgR/8AG68ER55\nJF3w1ZqIdCl78yX/Tz0Ff/d3qWZhZtYeB0KFu/fedLHJI4/AgQeWuzRmVss6Ewi+W0w3eegh+Pu/\nT1cUOwzMrBL55sHdYOHCdDfPn/883fbZzKwSORBKbMWKNDLommvSbaLNzCqVA6GEXn89hcGFF8K5\n55a7NGZmbXOncom88w6MHJm+tvC66zxM1My6l0cZVYimJjjnnPRz+nRfQGZm3c+jjCpABHzzm+mb\nwGbNchiYWfVwIBTZtdem7xt++GHYeedyl8bMrHAOhCK66y74/vfThWcDB7Y/v5lZJXEgFMns2ekq\n5P/5Hxg6tNylMTPrOA87LYIFC2DsWLjnHvjAB8pdGjOzznEgdNHy5fDpT6cvwvYXuZlZNXMgdMH6\n9enLai69NH0JtplZNfN1CJ301ltwxhnpuwr+4z/KXRozsx35wrRu0tiYbla3884wbRr0cj3LzCqM\nL0zrBhFw0UXpu43vusthYGa1w4HQQVddBX/4Q/p+g379yl0aM7PicSB0wNSp8JOfpO87HjCg3KUx\nMysu9yEUaObM9H3G9fVw+OHlLo2ZWdvch1Ai8+al7zO47z6HgZnVLneJtmPFCvjMZ+Cmm+Ckk8pd\nGjOz0nGTURsi0jeenXQS/Mu/lKUIZmad0pkmI9cQ2nDLLfDaazBxYrlLYmZWeq4htOLll+HYY9Nd\nTH3DOjOrNq4hFEkEfOUr8PWvOwzMrOdwILTg5pvTjesmTCh3SczMuk9BgSBplKTFkpZIetdpUtIw\nSQ9KWiBptqT9ct77b0kbJM3IW+Y2SS9IekbS05I+2PXd6brly+Hb304XofXxoFwz60HaDQRJvYAb\ngJHAkcA5kg7Lm+17wO0RcRTwr8BVOe99Fzi3ldV/MyKOjohjIuKPHS59kTU3FV1yCRx5ZLlLY2bW\nvQqpIRwHLI2I5RGxBZgOnJk3zxHAHICIqM99PyLmAG90Yfvd5qab0k3rLr203CUxM+t+hZyQhwCv\n5LxekU3LNR8YAyBpDLCbpEK+Zv4KSfMlXSOpbyEFLpWXXoLLL4fbb3dTkZn1TMU69V0K3CBpPPAQ\nsBJobGeZiRGxJguCm4EJwBUtzTh58uRtz+vq6qgr8ndVNjXBl78M3/oWHHFEUVdtZtYt6uvrqa+v\n79I62r0OQdLxwOSIGJW9nghERFzdyvz9gUURMSxn2sdI/QWfbWWZVt/vjusQfvSjVDN45BHXDsys\nNpTqOoS5wHBJB0jaCRgL5I8YGiSpecOXAbfmly175C4zOPsp4HPAcx0peLG8+GK6LYWbisysp2s3\nECKiEbgQmAUsBKZHxCJJUySNzmarAxokLQb2Ba5sXl7SQ8DdwMclvSzpjOytOyUtABYAg2iluaiU\nmpuK/umffBdTM7MefeuKH/4Qfvaz9A1ovXuXZBNmZmXRmSajHhsIL7wAxx2XwuCw/KsqzMyqnO9l\nVKCmJrjggnQXU4eBmVnSIwNh2jR4+234xjfKXRIzs8rR48bVRMB//if8+7+738DMLFePqyE8/DBs\n3gyf+ES5S2JmVll6XCBcfz1cdBH06nF7bmbWth41yujll+Hoo9N9i3bfvSirNDOrSB5l1I4bb4Rx\n4xwGZmYt6TE1hM2b4YAD4Ikn4OCDi1AwM7MK5hpCG6ZNgxNPdBiYmbWmRwRCxPbOZDMza1mPCITZ\ns9PPj3+8vOUwM6tkPSIQmmsH6lBrmplZz1LzncrLlsHxx8Py5bDrrkUsmJlZBXOncgtuvDHdyM5h\nYGbWtpquIfzlL3DggfD002nIqZlZT+EaQp477oDTTnMYmJkVombvdtrUBD/4Adx0U7lLYmZWHWq2\nhjBrFuy8M5xySrlLYmZWHWo2EK6/Hi6+2ENNzcwKVZOdyg0NcOqpaajpzjuXqGBmZhXMncqZG26A\nr37VYWBm1hE1V0PYuBEOOgiefRaGDClhwczMKphrCMBtt8HIkQ4DM7OOqqkaQmMjHHpoutX1CSeU\nuGBmZhWsx9cQfvtbGDQo3bvIzMw6pqYCwXc1NTPrvJppMlq4EE4/HV56Cfr1K325zMwqWcmajCSN\nkrRY0hJJE1p4f5ikByUtkDRb0n457/23pA2SZuQtc6Ckx7N13iWpS7fRuPNOGD/eYWBm1lntBoKk\nXsANwEjgSOAcSYflzfY94PaIOAr4V+CqnPe+C5zbwqqvBq6JiEOB14Evd7z42zU0wIc+1JU1mJn1\nbIXUEI4DlkbE8ojYAkwHzsyb5whgDkBE1Oe+HxFzgDdaWO/HgV9mz6cCn+9QyfM8/zwMH96VNZiZ\n9WyFBMIQ4JWc1yuyabnmA2MAJI0BdpM0sLUVShoEbIiIppx17tfa/O2JcCCYmXVVsW5/fSlwg6Tx\nwEPASqCxSOtm8uTJ257X1dVRV1e3w/t//jP07w8DBhRri2Zm1aW+vp76+vouraPdUUaSjgcmR8So\n7PVEICLi6lbm7w8siohhOdM+BnwzIj6bM+1VYHBENGXbmBQRn2xhfe2OMnr4YZgwAR59tM3ZzMx6\njFKNMpoLDJd0gKSdgLFA/oihQdK20f+XAbfmly175JoDfCF7Pg64vyMFz+XmIjOzrms3ECKiEbgQ\nmAUsBKZHxCJJUySNzmarAxokLQb2Ba5sXl7SQ8DdwMclvSzpjOyticAlkpYAewG3dHYnHAhmZl1X\nExemffGLcOaZ8KUvdVOhzMwqXI+9l5FrCGZmXVf1geAhp2ZmxVH1gbB2LfTuDXvtVe6SmJlVt6oP\nBNcOzMyKw4FgZmaAA8HMzDIOBDMzAxwIZmaWqfpAWLrUgWBmVgxVHQjr18PWrbDPPuUuiZlZ9avq\nQGhuLlKHLs42M7OW1EQgmJlZ1zkQzMwMcCCYmVmm6gPhkEPKXQozs9pQ9YHgGoKZWXFUbSBs3Ahv\nvgmDB5e7JGZmtaFqA2HZMg85NTMrpqoNBDcXmZkVlwPBzMwAB4KZmWUcCGZmBjgQzMwso4godxna\nJCnyy/jmm7D33ulnr6qNNDOz0pFERHRoHGZVnk6XLYODD3YYmJkVU1WeUt1cZGZWfA4EMzMDHAhm\nZpYpKBAkjZK0WNISSRNaeH+YpAclLZA0W9J+Oe+Ny5ZrkHR+zvQ52TqfkfS0pL0LLbQDwcys+Nod\nZSSpF7AEGAGsAuYCYyNicc489wAzImKapDrggog4X9JA4CngGEDAPOCYiNgoaQ5wSUQ808723zXK\naNgw+N//hYMO6tjOmpn1FKUaZXQcsDQilkfEFmA6cGbePEcAcwAioj7n/ZHArIjYGBGvA7OAUR3c\n/g7eegtefRWGDu3okmZm1pZCTshDgFdyXq/IpuWaD4wBkDQG2C2rHeQvuzJv2Vuz5qLLCy3wiy/C\nAQdAnz6FLmFmZoUo1mn1UuAGSeOBh0gn/sZ2lvlSRKyW1B/4L0nnRsS0lmacPHnytud9+9YxfHhd\nMcpsZlYz6uvrqa+v79I6CulDOB6YHBGjstcTgYiIq1uZvz+wKCKGSRoL1EXE/8/e+zEwJyLuzltm\nHHBsRFzUwvp26EO49lp4+WW47rqO7KaZWc9Sqj6EucBwSQdI2gkYC8zI2/AgadtX1VwG3Jo9nwmc\nIWlA1oR0BjBTUm9Jg7Jl+wKjgecKKfDSpR5hZGZWCu0GQkQ0AheSOoQXAtMjYpGkKZJGZ7PVAQ2S\nFgP7Aldmy24A/o000ugJYErWudyPFAzzgadJ/RI3F1JgDzk1MyuNqru53UEHwe9/71AwM2tLZ5qM\nqioQ3nkH9tgD3ngD+vYtc8HMzCpYzd/t9KWX0vUHDgMzs+KrqkBw/4GZWek4EMzMDHAgmJlZxoFg\nZmaAA8HMzDJVM+x0yxbYbTfYtAn69St3qczMKltNDzt9+WV473sdBmZmpVI1geDmIjOz0nIgmJkZ\n4EAwM7OMA8HMzAAHgpmZZapi2OnWrUH//rB+Pey6a7lLZGZW+Wp22OmKFbDPPg4DM7NSqopAcHOR\nmVnpORDMzAxwIJiZWcaBYGZmgAPBzMwyVTHsdJddgldfTXc7NTOz9tXssNMBAxwGZmalVhWB4OYi\nM7PScyCYmRngQDAzs4wDwczMAAeCmZllCgoESaMkLZa0RNKEFt4fJulBSQskzZa0X85747LlGiSd\nnzP9GEl/zN67rq3tv+99HdklMzPrjHavQ5DUC1gCjABWAXOBsRGxOGeee4AZETFNUh1wQUScL2kg\n8BRwDCBgHnBMRGyU9ARwYUTMlfRb4PsRMbOF7UelXythZlZpSnUdwnHA0ohYHhFbgOnAmXnzHAHM\nAYiI+pz3RwKzImJjRLwOzAJGSRoM7B4Rc7P57gA+15GCm5lZcRUSCEOAV3Jer8im5ZoPjAGQNAbY\nLasd5C+7Mps2JFtPW+s0M7NuVKxO5UuBOknzgFNIJ/7GIq3bzMy6QZ8C5lkJDMt5vX82bZuIWA2c\nBSCpP3BWRGyStBKoy1t2Trb80LbWmWvy5MnbntfV1VFXV9farGZmPVJ9fT319fVdWkchncq9gQZS\np/Jq4EngnIhYlDPPIGB9RISkK4CtETE5r1O5V/b82Ih4XdLjwEWkTurfANdHxO9a2L47lc3MOqgk\nncoR0QhcSOoQXghMj4hFkqZIGp3NVgc0SFoM7AtcmS27Afg3UhA8AUzJOpcB/gG4hTSCaWlLYWBm\nZt2nKm5/XellNDOrNDV7+2szMys9B4KZmQEOBDMzyzgQzMwMcCCYmVnGgWBmZoADwczMMg4EMzMD\nHAhmZpZxIJiZGeBAMDOzjAPBzMwAB4KZmWUcCGZmBjgQzMws40AwMzPAgWBmZhkHgpmZAQ4EMzPL\nOBDMzAxwIJiZWcaBYGZmgAPBzMwyDgQzMwMcCGZmlnEgmJkZ4EAwM7OMA8HMzIACA0HSKEmLJS2R\nNKGF94dKmi3paUnzJX0ym95X0q2S/ijpGUkfy1lmTrbOZ7Ll9i7ebpmZWUe1GwiSegE3ACOBI4Fz\nJB2WN9vlwN0RcQxwDvDDbPpXgYiIDwKfAK7JW+6ciDg6Io6JiLVd2I+qVV9fX+4ilEwt7xt4/6pd\nre9fZxRSQzgOWBoRyyNiCzAdODNvniZgj+z5nsDK7PkRwGyAiHgNeF3Shzu4/ZpWy3+Utbxv4P2r\ndrW+f51RyAl5CPBKzusV2bRcU4DzJL0CPAD8YzZ9AfBZSb0lHQQcCwzNWe7WrLno8k6V3szMiqZY\nn9DPAW6LiKHAp4Fp2fRbSbWFucC1wCNAY/belyLiKOAU4BRJ5xapLGZm1gmKiLZnkI4HJkfEqOz1\nRFK/wNU58zwHjIyIldnrZcBH8/sFJD0CfDkiFudNHwccGxEXtbD9tgtoZmYtigh1ZP4+BcwzFxgu\n6QBgNTCWVCPItRw4HZgq6XCgX0SslbQLKXQ2SzoD2BIRiyX1BvaMiHWS+gKjgd8XY4fMzKxz2g2E\niGiUdCEwi9TEdEtELJI0BZgbEQ8A3wJulvQNUgfzuGzxfYGZkhpJTUfnZdP7ZdP7AL2BB4Gbi7hf\nZmbWQe02GZmZWc9QscM+27sYrtpJeknSguzCvCfLXZ6uknSLpDWS/pgzbaCkWZIaJM2UNKCcZeyK\nVvZvkqQV2Ui5pyWNKmcZO0vS/tmFpQslPSvpomx6TRy/FvbvH7PptXL8+kl6IjuXPCtpUjb9QEmP\nZ+fQu7IWmbbXVYk1hOxiuCXACGAVqR9jbH5ndDWT9AKpI31DuctSDJJOBt4A7sguRETS1cC6iPhu\nFuoDI2JiOcvZWa3s3yTgLxFxbVkL10WSBgODI2K+pN2AeaRrjf4fNXD82ti/L1IDxw9A0q5ZX21v\n0mjOi4FLgHsj4heSfgTMj4iftLWeSq0hFHIxXLUTlfv777CI+AOQH25nAlOz51OBz3VroYqolf2D\ndByrWkT8OSLmZ8/fABYB+1Mjx6+V/Wu+lqrqjx9ARGzOnvYj9Q0HcBrwy2z6VODz7a2nUk9IhVwM\nV+2C1LE+V9JXy12YEtk3ItZA+qckDTKoNf+Q3b/rp9XapJJL0oHAh4DHgffU2vHL2b8nskk1cfwk\n9ZL0DPBn0ojNZcDrEdGUzbIC2K+99VRqIPQEJ0XEh4FPkf4oTy53gbpB5bVPds0PgfdFxIdI/4hV\n3fSQNafcC1ycfZLOP15Vffxa2L+aOX4R0RQRR5NqdscB+febK0ilBsJKYFjO6/3Zfn+kmhARq7Of\nrwG/Ih3EWrNG0ntgWzvuq2UuT1FFxGuxvRPuZuAj5SxPV2QdjvcCP4uI+7PJNXP8Wtq/Wjp+zSJi\nE1APnADsmfXHQoHn0EoNhG0Xw0naiXQx3Iwyl6loJO2afVpBUn/SnWCfK2+pikLs2CY7AxifPR8H\n3J+/QJXZYf+yk2SzMVT3MbwV+FNEfD9nWi0dv3ftX60cP0l7Nzd3ZRcDnwH8CZgDfCGbraDjV5Gj\njCANOwW+z/aL4a4qc5GKJrvR369IVfA+wJ3Vvn+Sfg7UAYOANcAk4D7gF6QbGi4Hzo6I18tVxq5o\nZf9OI7VHNwEvAV9rbnOvJpJOAh4CniX9TQbwz8CTwD1U+fFrY/++RG0cvw+QOo17ZY+7I+LK7Dwz\nHRgIPAOcmw3SaX1dlRoIZmbWvSq1ycjMzLqZA8HMzAAHgpmZZRwIZmYGOBDMzCzjQDAzM8CBYGZm\nGQeCmZkB8H9kuGpt8x6oNAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f67cf537e90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# as you can see, in this case there was little advantage to training past ten iterations\n",
    "tagger_base.plot_learning_curve(constants.JA_DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats_competitive_ja,\n",
    "                               theta_best_avp_hist_ja,\n",
    "                               all_tags_ja);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JA dev set\n",
      "0.920040372323\n"
     ]
    }
   ],
   "source": [
    "print('JA dev set')\n",
    "dev_results = tagger_base.eval_tagging_model(constants.JA_DEV_FILE,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats_competitive_ja,\n",
    "                               theta_best_avp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'avp-words-best.ja.preds')\n",
    "print(dev_results)\n",
    "tagger_base.apply_tagging_model(constants.JA_TEST_FILE_HIDDEN,\n",
    "                               tagger_base.classifier_tagger,\n",
    "                               features.word_feats_competitive_ja,\n",
    "                               theta_best_avp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'avp-words-best-te.ja.preds')\n",
    "\n",
    "# SUBMIT KAGGLE-avp-bakeoff1-ja-test.csv TO: https://kaggle.com/join/gtclassificationtaggingja\n",
    "kaggle.kaggle_output(constants.JA_TEST_FILE_HIDDEN,\n",
    "                                tagger_base.classifier_tagger,\n",
    "                                features.word_feats_competitive_ja,\n",
    "                                theta_best_avp_ja,\n",
    "                                all_tags_ja,\n",
    "                                'KAGGLE-avp-bakeoff1-ja-test.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8788213627992634"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.JA_TEST_FILE,'avp-words-best-te.ja.preds'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Structure prediction\n",
    "\n",
    "We now want to incorporate the Viterbi algorithm into the part of speech tagger.\n",
    "\n",
    "If you completed problem set 2, you can do this directly: just replace `tagger_base.classifier_tagger` with `viterbi.viterbi_tagger`. If the feature sets don't use any tag-transition features, then the outputs should be exactly the same.\n",
    "\n",
    "**Deliverable 3.1** Verify that this works, using `features.word_feats`. If your code from pset2 was written correctly, you don't actually have to do anything here. The test `test_viterbi_is_same_d3_1` will test this.\n",
    "\n",
    "(*0.5 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(viterbi); # just in case you need to modify it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2\n"
     ]
    }
   ],
   "source": [
    "theta_toy_one_inst_classifier,_ = structure_perceptron.estimate_perceptron(toy_data,\n",
    "                                                                features.word_feats,\n",
    "                                                                tagger_base.classifier_tagger,\n",
    "                                                                3,\n",
    "                                                                all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2\n"
     ]
    }
   ],
   "source": [
    "theta_toy_one_inst_viterbi,_ = structure_perceptron.estimate_perceptron(toy_data,\n",
    "                                                                features.word_feats,\n",
    "                                                                viterbi.viterbi_tagger,\n",
    "                                                                3,\n",
    "                                                                all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta_toy_one_inst_classifier == theta_toy_one_inst_viterbi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main advantage of using the Viterbi algorithm for structure prediction is that you can use features that look at more than one tag at a time. \n",
    "\n",
    "**Deliverable 3.2** Implement `features.hmm_feats`. This will be very similar to `hmm.hmm_features` from problem set 2, we've only changed some of the constants.\n",
    "(*0.5 points*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(['They', 'can', 'fish'], ['PRON', 'AUX', 'VERB']),\n",
       " (['the', 'old', 'man', 'the', 'boat'],\n",
       "  ['DET', 'NOUN', 'VERB', 'DET', 'NOUN'])]"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toy_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{('PRON', '--CURR-WORD--', 'They'): 1, ('PRON', '--PREV-TAG--', '--START--'): 1}\n",
      "{('AUX', '--CURR-WORD--', 'can'): 1, ('AUX', '--PREV-TAG--', 'PRON'): 1}\n",
      "{('VERB', '--CURR-WORD--', 'fish'): 1, ('VERB', '--PREV-TAG--', 'AUX'): 1}\n",
      "{('--END--', '--PREV-TAG--', 'VERB'): 1}\n"
     ]
    }
   ],
   "source": [
    "print(features.hmm_feats(toy_data[0][0],'PRON',constants.START_TAG,0))\n",
    "print(features.hmm_feats(toy_data[0][0],'AUX','PRON',1))\n",
    "print(features.hmm_feats(toy_data[0][0],'VERB','AUX',2))\n",
    "print(features.hmm_feats(toy_data[0][0],constants.END_TAG,'VERB',3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Deliverable 3.3** Evaluate the performance of this structured perceptron on the dev data.\n",
    "\n",
    "This will be slower than the perceptrons that you have trained in the earlier parts of this assignment.\n",
    "\n",
    "(*0.5 points for 4650, 0.25 points for 7650*)\n",
    "\n",
    "This cell takes three minutes to execute on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14\n"
     ]
    }
   ],
   "source": [
    "#English\n",
    "theta_hmm_sp,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set,\n",
    "                                         features.hmm_feats,\n",
    "                                         viterbi.viterbi_tagger,\n",
    "                                         15,\n",
    "                                         all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EN dev set\n",
      "0.872102318145\n"
     ]
    }
   ],
   "source": [
    "print('EN dev set')\n",
    "dev_results = tagger_base.eval_tagging_model(constants.DEV_FILE,\n",
    "                               viterbi.viterbi_tagger,\n",
    "                               features.hmm_feats,\n",
    "                               theta_hmm_sp,\n",
    "                               all_tags,\n",
    "                               'sp-hmm.preds')\n",
    "print(dev_results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is better than many of the fancier feature sets that we tried using the classification-based tagger. \n",
    "\n",
    "That's the power of structured prediction!\n",
    "\n",
    "Now let's try Japanese. This cell takes a little more than two minutes to run on my laptop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14\n"
     ]
    }
   ],
   "source": [
    "#Japanese\n",
    "theta_hmm_sp_ja,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set_ja,\n",
    "                                         features.hmm_feats,\n",
    "                                         viterbi.viterbi_tagger,\n",
    "                                         15,\n",
    "                                         all_tags_ja)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JA dev set\n",
      "0.806773578558\n"
     ]
    }
   ],
   "source": [
    "print('JA dev set')\n",
    "dev_results = tagger_base.eval_tagging_model(constants.JA_DEV_FILE,\n",
    "                               viterbi.viterbi_tagger,\n",
    "                               features.hmm_feats,\n",
    "                               theta_hmm_sp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'sp-hmm.ja.preds')\n",
    "print(dev_results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The improvement for Japanese is much more limited."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bakeoff #2\n",
    "\n",
    "**Deliverable 3.4** Implement the best features that you can for English and Japanese, this time using structured prediction with viterbi tagging.\n",
    "\n",
    "Make sure to save the output in the following files:\n",
    "\n",
    "- **English dev**: `sp-best.preds`\n",
    "- **English test**: `sp-best-te.preds`\n",
    "- **Japanese dev**: `sp-best.ja.preds`\n",
    "- **Japanese test**: `sp-best-te.ja.preds`\n",
    "\n",
    "Grading:\n",
    "- Full credit (0.5 points) for **89.5%** accuracy on English dev set, half credit (0.25 points) for **88.5%** accuracy.\n",
    "- Full credit (0.5 points) for **91%** accuracy on Japanese dev set, half credit (0.25 points) for **90%** accuracy.\n",
    "- +0.1 for beating my test set score on English\n",
    "- +0.1 for beating my test set score on Japanese\n",
    "- +0.2 for top English test set score in 4650\n",
    "- +0.2 for top English test set score in 7650\n",
    "- +0.2 for top Japanese test set score in 4650\n",
    "- +0.2 for top Japanese test set score in 7650\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kaggle Notes\n",
    "Refer back to the Kaggle note under Bakeoff #1 if you need a reminder what to do.\n",
    "If you would like to implement a better tagger such as Conditional Random Fields in order to compete in the competition, you may do that.  If you just want to feature engineer structured perceptron, that is fine.\n",
    "You may *NOT* use outside libraries like Scikit-Learn or TensorFlow if you decide to create an alternate tagger"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "reload(features);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29\n"
     ]
    }
   ],
   "source": [
    "theta_best_sp,theta_best_sp_hist =\\\n",
    "structure_perceptron.estimate_perceptron(training_set,\n",
    "                                         features.hmm_feats_competitive_en,\n",
    "                                         viterbi.viterbi_tagger,\n",
    "                                         30,\n",
    "                                         all_tags)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43028"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len([val for val in theta_best_sp.values() if val != 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "EN dev set\n",
      "0.903477218225\n"
     ]
    }
   ],
   "source": [
    "print('EN dev set')\n",
    "dev_results = tagger_base.eval_tagging_model(constants.DEV_FILE,\n",
    "                               viterbi.viterbi_tagger,\n",
    "                               features.hmm_feats_competitive_en,\n",
    "                               theta_best_sp,\n",
    "                               all_tags,\n",
    "                               'sp-best.preds')\n",
    "print(dev_results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tagger_base.apply_tagging_model(constants.TEST_FILE_HIDDEN,\n",
    "                                viterbi.viterbi_tagger,\n",
    "                                features.hmm_feats_competitive_en,\n",
    "                                theta_best_sp,\n",
    "                                all_tags,\n",
    "                                'sp-best-te.preds')\n",
    "\n",
    "# SUBMIT KAGGLE-sp-bakeoff2-en-test.csv to https://kaggle.com/join/gt46507650spenpset3\n",
    "kaggle.kaggle_output(constants.TEST_FILE_HIDDEN,\n",
    "                                viterbi.viterbi_tagger,\n",
    "                                features.hmm_feats_competitive_en,\n",
    "                                theta_best_sp,\n",
    "                                all_tags,\n",
    "                                'KAGGLE-sp-bakeoff2-en-test.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8873505349276274"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.TEST_FILE,'sp-best-te.preds'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "43028"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len([val for val in theta_best_sp.values() if val != 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Japanese"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29\n"
     ]
    }
   ],
   "source": [
    "theta_best_sp_ja,_ =\\\n",
    "structure_perceptron.estimate_perceptron(training_set_ja,\n",
    "                                         features.hmm_feats_competitive_ja,\n",
    "                                         viterbi.viterbi_tagger,\n",
    "                                         30,\n",
    "                                         all_tags_ja)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "67002"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# number of features\n",
    "len([val for val in theta_best_sp_ja.values() if val != 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JA dev set\n",
      "0.921273971067\n"
     ]
    }
   ],
   "source": [
    "print('JA dev set')\n",
    "dev_results = tagger_base.eval_tagging_model(constants.JA_DEV_FILE,\n",
    "                               viterbi.viterbi_tagger,\n",
    "                               features.hmm_feats_competitive_ja,\n",
    "                               theta_best_sp_ja,\n",
    "                               all_tags_ja,\n",
    "                               'sp-best.ja.preds')\n",
    "print(dev_results)\n",
    "tagger_base.apply_tagging_model(constants.JA_TEST_FILE_HIDDEN,\n",
    "                                viterbi.viterbi_tagger,\n",
    "                                features.hmm_feats_competitive_ja,\n",
    "                                theta_best_sp_ja,\n",
    "                                all_tags_ja,\n",
    "                                'sp-best-te.ja.preds')\n",
    "\n",
    "# SUBMIT KAGGLE-sp-bakeoff2-ja-test.csv to https://kaggle.com/join/gtcs46507650pset3ja\n",
    "kaggle.kaggle_output(constants.JA_TEST_FILE_HIDDEN,\n",
    "                                viterbi.viterbi_tagger,\n",
    "                                features.hmm_feats_competitive_ja,\n",
    "                                theta_best_sp_ja,\n",
    "                                all_tags_ja,\n",
    "                                'KAGGLE-sp-bakeoff2-ja-test.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.879926335174954"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can't run this\n",
    "scorer.accuracy(scorer.get_confusion(constants.JA_TEST_FILE,'sp-best-te.ja.preds'))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
